#include <iostream>
#include <vector>
#include "utils.h"
using namespace std;

void permute(std::vector<std::vector<int>> &res,
             std::vector<int> &nums,
             int idx) {
    if (idx == nums.size() - 1) {
        res.emplace_back(nums);
        return;
    }
    for (int i = idx; i < nums.size(); ++i) {
        swap(nums, i, idx);
        permute(res, nums, idx + 1);
        swap(nums, i, idx);
    }
}

void permute_II(std::vector<std::vector<int>> &res,
                std::vector<int> &nums,
                int idx) {
    if (idx == nums.size() - 1) {
        res.emplace_back(nums);
        return;
    }
    for (int i = idx; i < nums.size(); ++i) {
        if (i != idx && nums[i] == nums[idx]) {
            continue;
        }
        swap(nums, i, idx);
        permute_II(res, nums, idx + 1);
        swap(nums, i, idx);
    }
}

int main() {
    std::vector<int> input = {1, 2, 3};

    std::vector<std::vector<int>> ret;
    permute(ret, input, 0);
    printVec("permute", ret);

    input = {1, 3, 1};
    ret.clear();
    permute_II(ret, input, 0);
    printVec("permute_II", ret);
    return 0;
}
